{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Frequency of the Most Frequent Element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #prefix-sum #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #前缀和 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxFrequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最高频元素的频数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>元素的 <strong>频数</strong> 是该元素在一个数组中出现的次数。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。在一步操作中，你可以选择 <code>nums</code> 的一个下标，并将该下标对应元素的值增加 <code>1</code> 。</p>\n",
    "\n",
    "<p>执行最多 <code>k</code> 次操作后，返回数组中最高频元素的 <strong>最大可能频数</strong> <em>。</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4], k = 5\n",
    "<strong>输出：</strong>3<strong>\n",
    "解释：</strong>对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。\n",
    "4 是数组中最高频元素，频数是 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,4,8,13], k = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>存在多种最优解决方案：\n",
    "- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。\n",
    "- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。\n",
    "- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,9,6], k = 2\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= k <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [frequency-of-the-most-frequent-element](https://leetcode.cn/problems/frequency-of-the-most-frequent-element/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [frequency-of-the-most-frequent-element](https://leetcode.cn/problems/frequency-of-the-most-frequent-element/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4]\\n5', '[1,4,8,13]\\n5', '[3,9,6]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxFrequency(self, nums, k):\n",
    "        maxFrequency = 0  # Initialize the maximum frequency\n",
    "        currentSum = 0  # Initialize the current sum of the subarray elements\n",
    "\n",
    "        nums.sort()  # Sort the array in ascending order\n",
    "\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            currentSum += nums[right]  # Include the current element in the subarray sum\n",
    "\n",
    "            # Check if the current subarray violates the condition (sum + k < nums[right] * length)\n",
    "            while currentSum + k < nums[right] * (right - left + 1):\n",
    "                currentSum -= nums[left]  # Adjust the subarray sum by removing the leftmost element\n",
    "                left += 1  # Move the left pointer to the right\n",
    "\n",
    "            # Update the maximum frequency based on the current subarray length\n",
    "            maxFrequency = max(maxFrequency, right - left + 1)\n",
    "\n",
    "        return maxFrequency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        top = max(nums)\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 排序\n",
    "        cnt = [0] * (top+1)\n",
    "        for i in nums:\n",
    "            cnt[i] += 1\n",
    "        idx = 0\n",
    "        for i in range(top+1):\n",
    "            for x in range(cnt[i]):\n",
    "                nums[idx] = i\n",
    "                idx += 1\n",
    "        \n",
    "        prev_cnt = prev_num = 0\n",
    "        i = 0\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            while i+1 < n and nums[i+1] == nums[i]:\n",
    "                i += 1\n",
    "            k -= prev_cnt * (nums[i] - prev_num)\n",
    "            prev_num = nums[i]\n",
    "            while k < 0:\n",
    "                k += prev_num-nums[l]\n",
    "                l += 1\n",
    "            prev_cnt = i-l+1\n",
    "            ans = max(ans, prev_cnt)\n",
    "            i += 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        max_val = max(nums)\n",
    "        cnt = [0] * (max_val + 1)\n",
    "        for val in nums:\n",
    "            cnt[val] += 1\n",
    "        pos = 0\n",
    "        for i in range(max_val, 0, -1):\n",
    "            for j in range(cnt[i]):\n",
    "                nums[pos] = i\n",
    "                pos += 1\n",
    "\n",
    "        sum_val = 0\n",
    "        j = -1\n",
    "        ans = 0\n",
    "\n",
    "        def check(i, pos):\n",
    "            nonlocal sum_val, k\n",
    "            new_sum = sum_val + nums[pos]\n",
    "            new_len = pos - i + 1\n",
    "            return new_len * nums[i] - new_sum <= k\n",
    "\n",
    "        for i in range(n):\n",
    "            while j + 1 < n and check(i, j + 1):\n",
    "                j += 1\n",
    "                sum_val += nums[j]\n",
    "            ans = max(ans, j - i + 1)\n",
    "            sum_val -= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        from collections import deque\n",
    "        st = deque()\n",
    "\n",
    "        max_freq = 0\n",
    "        k_left = k\n",
    "        last_checked_num = None\n",
    "\n",
    "        while nums:\n",
    "            base = nums[-1]\n",
    "            last_checked_num = base\n",
    "            \n",
    "            while nums:\n",
    "                num = nums.pop()\n",
    "                if k_left - (base - num) >= 0:\n",
    "                    st.appendleft(num)\n",
    "                    k_left = k_left - (base - num)\n",
    "                else:\n",
    "                    nums.append(num)\n",
    "                    break\n",
    "            \n",
    "            max_freq = max(max_freq, len(st))\n",
    "            break\n",
    "        \n",
    "        while nums:\n",
    "            while st and st[-1] == last_checked_num:\n",
    "                st.pop()\n",
    "            \n",
    "            if st:\n",
    "                base = st[-1]\n",
    "                k_left = k_left + len(st) * (last_checked_num - base)\n",
    "            else:\n",
    "                base = nums[-1]\n",
    "                k_left = k\n",
    "            \n",
    "            last_checked_num = base\n",
    "            while nums:\n",
    "                num = nums.pop()\n",
    "                if k_left - (base - num) >= 0:\n",
    "                    st.appendleft(num)\n",
    "                    k_left = k_left - (base - num)\n",
    "                else:\n",
    "                    nums.append(num)\n",
    "                    break            \n",
    "\n",
    "            max_freq = max(max_freq, len(st))\n",
    "        \n",
    "        return max_freq\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l, r, n, s = 0, 0, len(nums), 0\n",
    "        ret = 0\n",
    "        while r < n:\n",
    "            s += nums[r]\n",
    "            while nums[r] * (r - l + 1) - s > k:\n",
    "                s -= nums[l]\n",
    "                l += 1\n",
    "            ret = max(ret, r - l + 1)\n",
    "            r += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        total = 0\n",
    "        res = 1\n",
    "        for r in range(1, n):\n",
    "            total += (nums[r] - nums[r - 1]) * (r - l)\n",
    "            while total > k:\n",
    "                total -= nums[r] - nums[l]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        total = 0\n",
    "        res = 1\n",
    "        for r in range(1, n):\n",
    "            total += (nums[r] - nums[r - 1]) * (r - l)\n",
    "            while total > k:\n",
    "                total -= nums[r] - nums[l]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        l = 0\n",
    "\n",
    "        cur_sum = 0\n",
    "\n",
    "        for r in range(len(nums)):\n",
    "            cur_max = nums[r]\n",
    "\n",
    "            cur_sum += nums[r]\n",
    "\n",
    "            product = cur_max * (r - l + 1)\n",
    "\n",
    "            increaments_needed = product - cur_sum\n",
    "\n",
    "            # condition to move l pointer\n",
    "            while increaments_needed > k:\n",
    "                cur_sum -= nums[l]\n",
    "                l += 1\n",
    "                product = cur_max * (r - l + 1)\n",
    "                increaments_needed = product - cur_sum\n",
    "            \n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        ans = 1\n",
    "        cost = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            if right == 0:\n",
    "                continue\n",
    "            diff = num - nums[right - 1]\n",
    "            cost += diff * (right - left)\n",
    "            while left < right and cost > k:\n",
    "                cost -= num - nums[left]\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, l, res, s = 0, 0, len(nums), 0, nums[0]\n",
    "        while right < l:\n",
    "            if k >= nums[right] * (right - left + 1) - s:\n",
    "                res = max(res, right - left + 1)\n",
    "                right += 1\n",
    "                if right < l:\n",
    "                    s += nums[right]\n",
    "            else:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        total = 0\n",
    "        res = 1\n",
    "        for r in range(1, n):\n",
    "            total += (nums[r] - nums[r - 1]) * (r - l)\n",
    "            while total > k:\n",
    "                total -= nums[r] - nums[l]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        total = 0\n",
    "        res = 1\n",
    "\n",
    "        for r in range(1, n):\n",
    "            total += (nums[r] - nums[r - 1]) * ( r - l )\n",
    "\n",
    "            while total > k:\n",
    "                total -= nums[r] - nums[l]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        left = 0\n",
    "        right = 1\n",
    "        kk = 0\n",
    "        maxWindowSize = 1\n",
    "        while right < len(nums):\n",
    "            ## make a window such that all values equal to right bound\n",
    "            ## find maximum window size\n",
    "            ## move window right increment (bound after - bound before) * size\n",
    "            kk += (nums[right] - nums[right-1]) * (right - left)\n",
    "            # find optimal left bound\n",
    "            while kk > k:\n",
    "                kk -= nums[right] - nums[left]\n",
    "                left += 1\n",
    "            # collect result\n",
    "            maxWindowSize = max(maxWindowSize, right - left + 1)\n",
    "            right += 1\n",
    "        return maxWindowSize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        curr = 0\n",
    "\n",
    "        for right in range(len(nums)):\n",
    "            target = nums[right]\n",
    "            curr += target\n",
    "\n",
    "            while (right - left + 1) * target - curr > k:\n",
    "                curr -= nums[left]\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, right - left + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        L = 0\n",
    "        window_sum = 0\n",
    "        for R in range(n):\n",
    "            window_sum += nums[R]\n",
    "            while window_sum + k < nums[R] * (R-L+1):\n",
    "                window_sum -= nums[L]\n",
    "                L += 1\n",
    "            res = max(res, R-L+1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            preSum[i + 1] = preSum[i] + nums[i]\n",
    "        preSum = preSum[1:]\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            if left > 0:\n",
    "                subSum = preSum[right] - preSum[left - 1]\n",
    "            else:\n",
    "                subSum = preSum[right]\n",
    "            while nums[right] * (right - left + 1) - subSum > k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxFrequency(self, nums, k):\n",
    "        nums.sort()\n",
    "\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "\n",
    "        res = 1\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] * (right - left) - (pre[right] - pre[left]) > k:\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
